题面

一棵 $n(n\le 5\times 10^4)$ 个节点的树，$q(q\le5\times 10^4)$ 次询问，每次询问 $[l,r]$ 区间中所有点和 $z$ 的公共祖先的深度和，即：

解题思路

离线后用树剖+线段树维护

真的不要往 $Lca$ 那方面想，虽然貌似有巨佬那样切掉了

分析

不难发现，一个点 $i$ 的深度可以用 $dis(i,root)+1$ 的表示，而两个点的 $Lca$ 到根节点的路径又是一致的，这样我们就可以把一个点到 $root$ 路径上的所有点权值 $+1$，这样是不是就可以表示一个点做出的贡献了。这样查询时，两点 $Lca$ 到根节点路径上的权值会被计算贡献，而其他的没有影响，这样就去除了 $Lca$ 的影响

然鹅现在是一个区间 $[l,r]$ 与节点 $z$ 的 $dep[Lca(i,z)]$ 之和。显然，如果能得出一个前缀答案的话，$[l,r]$ 的贡献即可表示为 $ans(r)-ans(l-1)$，能大大降低复杂度，因此我们可以按 $id$ 的顺序修改点到 $root$ 的路径的权值，对于询问则把每个询问拆成两个点，离线处理即可

更新某点到 $root$ 路径上点的权值可以用树链剖分维护，时间复杂度 $O(n\log^2n)$，加之树链剖分优秀的常数，这道题就很显然了

warning

由于题中需要取模，因此 $ans(r)-ans(l-1)$ 的值可能为负数

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define N 50003
using namespace std;
const int p=201314;
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int op,pos,val;
    node(int a,int b,int c):op(a),pos(b),val(c){}
    node(){}
}cur;
int head[N],n,m,t,ver[N],nxt[N],num,ans;
int seg[N],rev[N],top[N],f[N<<2],tag[N<<2];
int deep[N],size[N],son[N],fa[N],L,R,Ans[N];
queue<node>P[N];
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t;
}
inline int dec(rint x){return(x>=p)?x-p:x;}
inline int rec(rint x){return(x<0)?x+p:x;}
inline void dfs1(rint k) {
    rint i,to;
    deep[k]=deep[fa[k]]+1,size[k]=1;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i],fa[to]=k,dfs1(to),
        size[k]+=size[to];
        if(size[to]>size[son[k]])
            son[k]=to;
    }
}
inline void dfs2(rint k) {
    if(son[k]) {
        seg[son[k]]=++num,
        top[son[k]]=top[k],
        rev[num]=son[k],
        dfs2(son[k]);
    }
    rint i,to;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];if(top[to]) continue;
        seg[to]=++num,top[to]=rev[num]=to,dfs2(to);
    }
}
inline void push(rint k,rint l,rint r) {
    f[k]=(f[k]+(LL)(r-l+1)*tag[k])%p;
    if(l!=r) {
        rint ls=k<<1;
        tag[ls]+=tag[k],tag[ls|1]+=tag[k];
    }tag[k]=0;
}
inline void Modify(rint k,rint l,rint r) {
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {tag[k]=1;return push(k,l,r);}
    rint m=(l+r)>>1,ls=k<<1;
    Modify(ls,l,m),Modify(ls|1,m+1,r);
    f[k]=dec(f[ls]+f[ls|1]);
}
inline void Query(rint k,rint l,rint r) {
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {ans=(ans+f[k])%p;return;}
    rint m=(l+r)>>1,ls=k<<1;
    Query(ls,l,m),Query(ls|1,m+1,r);
}
#define fx top[x]
inline void Add(rint x) {
    while(fx!=1) {
        L=seg[fx],R=seg[x],
        Modify(1,1,n),x=fa[fx];
    }
    L=1,R=seg[x],Modify(1,1,n);
}
inline int Ask(rint x) {
    ans=0;
    while(fx!=1) {
        L=seg[fx],R=seg[x],
        Query(1,1,n),x=fa[fx];
    }
    L=1,R=seg[x],Query(1,1,n);
    return ans;
}
int main()
{
    rint i,l,r,op,pos,val;
    n=read(),m=read();
    for(i=2;i<=n;i++) add(read()+1,i);
    for(i=1;i<=m;i++) {
        l=read(),r=read()+1,val=read()+1;
        P[l].push(node(0,i,val)),//每个询问拆成两个
        P[r].push(node(1,i,val));
    }
    num=seg[1]=rev[1]=top[1]=1,dfs1(1),dfs2(1);//树剖
    for(i=1;i<=n;i++) {
        Add(i);//第i个点的贡献
        while(!P[i].empty()) {
            cur=P[i].front(),P[i].pop();
            op=cur.op,pos=cur.pos,val=cur.val;
            if(op) Ans[pos]+=Ask(val);//按照左右端点，计算贡献
            else Ans[pos]-=Ask(val);
        }
    }
    for(i=1;i<=m;i++) printf("%d\n",rec(Ans[i]));//注意可能为负数
    return 0;
}

devil.